package com.wtgroup.demo.mianshi.算法.排序;

/**
 * 计数排序
 */
public class CountSort {


    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 1, 5, 6, 5, 29, 15, 23, 56};
        int max = getMax(arr);
        int[] bucket = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }

        int k = 0;

        for (int i = 0; i < bucket.length; i++) {
            int cnt = bucket[i];
            while (cnt-- > 0) {
                arr[k++] = i;
            }
        }

        SortUtil.print(arr);
    }

    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(max<arr[i]) {
                max = arr[i];
            }
        }

        return max;
    }
}
